翻訳と辞書 Words near each other ・ Reconstructed newsreels by Georges Méliès ・ Reconstructing Womanhood ・ ReConStruction ・ Reconstruction ・ Reconstruction (2001 film) ・ Reconstruction (2003 film) ・ Reconstruction (album) ・ Reconstruction (architecture) ・ Reconstruction (band) ・ Reconstruction (law) ・ Reconstruction Acts ・ Reconstruction Agency ・ Reconstruction algorithm ・ Reconstruction Amendments ・ Reconstruction and Development Programme ・ Reconstruction conjecture ・ Reconstruction efforts after the Russo-Georgian War ・ Reconstruction Era ・ Reconstruction filter ・ Reconstruction Finance Corporation ・ Reconstruction from zero crossings ・ Reconstruction in Afghanistan ・ Reconstruction of automobile destruction ・ Reconstruction of Germany ・ Reconstruction of New Orleans ・ Reconstruction Party of Canada ・ Reconstruction Site ・ Reconstruction Treaties ・ Reconstructionism ・ Reconstructionist Judaism Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Reconstruction conjecture ： ウィキペディア英語版 Reconstruction conjecture Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly〔Kelly, P. J., (A congruence theorem for trees ), ''Pacific J. Math.'' 7 (1957), 961–968.〕 and Ulam.〔Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.〕 ==Formal statements== Given a graph $G\; =\; (V,E)$, a vertex-deleted subgraph of $G$ is a subgraph formed by deleting exactly one vertex from $G$. Clearly, it is an induced subgraph of $G$. For a graph $G$, the deck of G, denoted $D(G)$, is the multiset of all vertex-deleted subgraphs of $G$. Each graph in $D(G)$ is called a card. Two graphs that have the same deck are said to be hypomorphic. With these definitions, the conjecture can be stated as: * Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices are isomorphic. : (The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.) Harary〔Harary, F., On the reconstruction of a graph from a collection of subgraphs. In ''Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963)''. Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52.〕 suggested a stronger version of the conjecture: * Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic. Given a graph $G\; =\; (V,E)$, an edge-deleted subgraph of $G$ is a subgraph formed by deleting exactly one edge from $G$. For a graph $G$, the edge-deck of G, denoted $ED(G)$, is the multiset of all edge-deleted subgraphs of $G$. Each graph in $ED(G)$ is called an edge-card. * Edge Reconstruction Conjecture: (Harary, 1964)〔 Any two graphs with at least four edges and having the same edge-decks are isomorphic. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Reconstruction conjecture」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.